{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> 作者：Robert Cimrman"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "%matplotlib inline\n",
    "import numpy as np"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2.5.1 介绍\n",
    "\n",
    "(密集) 矩阵是:\n",
    "- 数据对象\n",
    "- 存储二维值数组的数据结构\n",
    "\n",
    "重要特征:\n",
    "- 一次分配所有项目的内存\n",
    "    - 通常是一个连续组块，想一想Numpy数组\n",
    "- *快速*访问个项目(*)\n",
    "\n",
    "### 2.5.1.1 为什么有稀疏矩阵？\n",
    "\n",
    "- 内存，增长是n**2\n",
    "- 小例子（双精度矩阵）:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<matplotlib.text.Text at 0x1122505c0>"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAaQAAAEKCAYAAABdWiGrAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAIABJREFUeJzt3Xl81NW9//HXJwlhh7ALAQQFVJQ9AlbbWhfEFay2xaqg\nxdJa7bV6+2u1y7V2u1p7q9ValbrhUpdaFWpViltvb1Uk7IsgARXCIkEgIlu2z++POdGRmSSTmFmS\nvJ+Pxzxm5nPO93vOlwn55Pv9njnH3B0REZF0y0p3B0REREAJSUREMoQSkoiIZAQlJBERyQhKSCIi\nkhGUkEREJCMoIYmISEZQQhIRkYyghCQiIhkhJ90dyHTdu3f3AQMGpLsbIiJNysKFC7e7e4/6bKOE\nVIcBAwZQWFiY7m6IiDQpZvZefbfRJTsREckISkgiIpIRlJBERCQjKCGJiEhGUEISEZEYO/aUpbzN\npCYkM7vazFaa2Qoze9TM2pjZQDObb2ZrzexxM8sNdVuH90WhfEDUfq4L8TVmdlpUfGKIFZnZtVHx\nerchIiIRf1u6mS/+5hVeXPV+SttNWkIys3zgP4ACdz8GyAamADcBt7j7YGAnMD1sMh3Y6e6DgFtC\nPcxsaNjuaGAi8EczyzazbOAO4HRgKHBBqEt92xARkYgVm0r5f08uZfeBCr75UCF/eHktqVpZPNmX\n7HKAtmaWA7QDtgAnAU+G8lnA5PB6UnhPKD/ZzCzEH3P3A+7+DlAEjA2PIndf7+5lwGPApLBNfdsQ\nEWnxSnYfYMaDhewvrwLAHX77j7e58s+LOVBRmfT2k5aQ3H0T8FtgA5FEVAosBHa5e0WoVgzkh9f5\nwMawbUWo3y06ftA2NcW7NaCNTzGzGWZWaGaFJSUlDTl8EZEmpayiiu88spDNpftjyqrcaZWV/CEH\nybxk14XIGclAoA/QnsjltYNVnwvGO1PxRozX1sanA+4z3b3A3Qt69KjXzBciIk2Ou3P9nJUseHdn\nTNmRh3Tkt18ZQVZW8i8mJTPlnQK84+4l7l4OPAV8DsgLl/AA+gKbw+tioB9AKO8M7IiOH7RNTfHt\nDWhDRKTFeviN93j0zQ0x8S7tWvGnqQW0b52aWeaSmZA2AOPNrF24T3MysAp4BTg/1JkGzA6v54T3\nhPKXPXInbQ4wJYyQGwgMBt4EFgCDw4i6XCIDH+aEberbhohIi/T6ug+44W+rYuI5WcYfLxxDv67t\nUtaXpKU9d59vZk8Ci4AKYDEwE/g78JiZ/TLE7g2b3As8ZGZFRM5apoT9rDSzJ4gkswrgCnevBDCz\nK4G5REbw3efuK8O+flifNkREWqKNO/ZyxZ8XUVEV+3f59WcP5bjDY26xJ5XpBKF2BQUFrtm+RaS5\n2XOggvPufI3VW3fHlF0wtj+/PvcYPssgZDNb6O4F9dlGMzWIiLQw7s73/7I0bjI6dkAXbjjn6M+U\njBpKCUlEpIW5/eUinl+xNSbep3Mb7rxoDLk56UkNSkgiIi3I3JVb+d28t2PibVplMXNqAd07tE5D\nryKUkEREWog1W3dzzeNL4pbdfP4IjsnvnOIefZoSkohIC7BzTxnffLCQPWWxUwB958TDOXtEnzT0\n6tOUkEREmrmKyiqufHQRG3bsjSk7+ciefH/CEWnoVSwlJBGRZu5Xz73Fv4s+iIkf3qM9t0wZmZJp\ngRKhhCQi0ow9UbiR+//9bky8U5sc7pl2LJ3atEp9p2qghCQi0kwtfG8nP3l6RUw8y+APXx/NwO7t\n09CrmikhiYg0Q1tK9/GthxZSVlkVU/ajM47iC0MybyUDJSQRkWZmf3kl33poIds/OhBT9uVR+Uw/\nYWAaelU3JSQRkWbE3bn2r8tYVlwaUzaiXx6//vKwtEwLlAglJBGRZuRP/1rPM0s2x8R7dmzNzIvH\n0KZVdhp6lRglJBGRZuLVNdu48fnVMfHc7CzuungMvTq1SUOvEqeEJCLSDKwr+YjvPrqYOEsb8esv\nD2N0/y6p71Q9JS0hmdkRZrYk6vGhmX3PzLqa2TwzWxueu4T6Zma3mVmRmS0zs9FR+5oW6q81s2lR\n8TFmtjxsc1tYmZaGtCEi0lR9uL+cbz5YyO79FTFl008YyPlj+qahV/WXtITk7mvcfaS7jwTGAHuB\np4FrgZfcfTDwUngPcDqR5ckHAzOAOyGSXIDrgXHAWOD66gQT6syI2m5iiNerDRGRpqqyyrnq0cWs\nL9kTU/b5wd257vQj09CrhknVJbuTgXXu/h4wCZgV4rOAyeH1JOBBj3gDyDOz3sBpwDx33+HuO4F5\nwMRQ1sndX/fIsrcPHrSv+rQhItIk3Tx3Da+sKYmJH9qtHbdfMIqc7KZzZyZVPZ0CPBpe93L3LQDh\nuWeI5wMbo7YpDrHa4sVx4g1pQ0SkyZm9ZBN3/XNdTLxD6xzumVpAXrvcNPSq4ZKekMwsFzgH+Etd\nVePEvAHxhrTx6UpmM8ys0MwKS0pi//IQEUm35cWl/ODJZTFxM7j1ayMZ3KtjGnr12aTiDOl0YJG7\nvx/ev199mSw8bwvxYqBf1HZ9gc11xPvGiTekjU9x95nuXuDuBT16ZN70GiLSsm3bvZ8ZDxVyoCJ2\nWqD/PHUIpwztlYZefXapSEgX8MnlOoA5QPVIuWnA7Kj41DASbjxQGi63zQUmmFmXMJhhAjA3lO02\ns/FhdN3Ug/ZVnzZERJqEAxWVXP7wIraU7o8pO3N4b6740qA09Kpx5CRz52bWDjgV+FZU+EbgCTOb\nDmwAvhLizwFnAEVERuRdCuDuO8zsF8CCUO/n7r4jvL4ceABoCzwfHvVuQ0SkKXB3/uuZlSx8b2dM\n2dDenbj5/OEZOy1QIiwyQE1qUlBQ4IWFhenuhogIs157l+vnrIyJd2ufy+wrj6dvl3Zp6FV8ZrbQ\n3Qvqs03TGQ8oItKCvVa0nZ8/uyomnpNl3HnRmIxKRg2lhCQikuE27tjLd/68iMo48wLdMOloxg7s\nmoZeNT4lJBGRDLbnQAXffLCQXXvLY8ouHNefC8cdmoZeJYcSkohIhqqqcq55Ygmrt+6OKRs7sCvX\nn310GnqVPEpIIiIZ6raX1zJ35fsx8fy8ttx54Whyc5rXr/DmdTQiIs3ECyu2cOuLa2PibVtlM3Pq\nGLp1aJ2GXiWXEpKISIZZvfVDrnliadyy335lBEf36ZziHqWGEpKISAbZsaeMy2YVsresMqbsuycN\n4szhzXeBAiUkEZEMUV5ZxRWPLKJ4576YslOO6sXVpwxJQ69SRwlJRCRD/PLZVby+/oOY+OCeHbjl\nayPIymq60wIlQglJRCQD3Pd/7zDr9fdi4p3btuKeaQV0bNMqDb1KLSUkEZE0e2pRcdxpgbIM7vj6\naA7t1j4NvUo9JSQRkTR6cdX7/L84C+0B/PjMoZwwuHuKe5Q+SkgiImkyf/0HXFHDHHUXjO3HN44f\nkPpOpZESkohIGqzYVMpls+Kv+nr6MYfwy8nDmvTaRg2hhCQikmLvbN/DJfe/ye4DFTFlxw/qxq1T\nRpLdzEfUxZPUhGRmeWb2pJmtNrO3zOw4M+tqZvPMbG147hLqmpndZmZFZrbMzEZH7WdaqL/WzKZF\nxceY2fKwzW1hKXMa0oaISCpsLd3PRffMZ/tHZTFlI/p25u6LC2idk52GnqVfss+Qfg+84O5HAiOA\nt4BrgZfcfTDwUngPcDowODxmAHdCJLkA1wPjgLHA9dUJJtSZEbXdxBCvVxsiIqmwa28ZF987n027\nYr/4OqhnB+6/dCwdWuekoWeZIWkJycw6AV8A7gVw9zJ33wVMAmaFarOAyeH1JOBBj3gDyDOz3sBp\nwDx33+HuO4F5wMRQ1sndX/fIOuwPHrSv+rQhIpJUew5UcMn9C1i77aOYsvy8tjw0fSxd2+emoWeZ\nI5lnSIcBJcD9ZrbYzO4xs/ZAL3ffAhCee4b6+cDGqO2LQ6y2eHGcOA1oQ0QkaQ5UVPLthxeyZOOu\nmLJu7XN5aPpYendum4aeZZZkJqQcYDRwp7uPAvbwyaWzeOLdwfMGxGuT0DZmNsPMCs2ssKSkpI5d\niojUrLLKuebxpfxr7faYsg6tc5j1jbEc1qNDGnqWeZKZkIqBYnefH94/SSRBvV99mSw8b4uq3y9q\n+77A5jrifePEaUAbn+LuM929wN0LevTokfABi4hEc3d+OnsFf1++JaYsNyeLP00t4Jj85rmUREMk\nLSG5+1Zgo5kdEUInA6uAOUD1SLlpwOzweg4wNYyEGw+Uhsttc4EJZtYlDGaYAMwNZbvNbHwYXTf1\noH3Vpw0RkUb323+s4c/zN8TEs7OMP1wwiuMO75aGXmWuZA/n+C7wiJnlAuuBS4kkwSfMbDqwAfhK\nqPsccAZQBOwNdXH3HWb2C2BBqPdzd98RXl8OPAC0BZ4PD4Ab69OGiEhju+df67njlXVxy246bzgT\njj4kxT3KfBYZoCY1KSgo8MLCwnR3Q0SakCcXFvP9v8Rf8fUnZx7FZZ8/LMU9Sj0zW+juBfXZRjM1\niIg0on+s3MoP/xp/stQrvnR4i0hGDaWEJCLSSN5Y/wFXPro47mSpXx/Xn+9POCLOVlJNCUlEpBFU\nT5ZaFmey1DOH9eYXk45pcZOl1pcSkojIZ7S+5COm3fcmH8WZLPXzg7vzu6+NaJGTpdaXEpKIyGew\npXQfF9/7Jh/siZ0sdWS/PO66aEyLnSy1vpSQREQaaOeeMi6+9824k6UO7tmB+y85lvYteLLU+lJC\nEhFpgI8OVHDJAwsoqnGy1HF0aeGTpdaXEpKISD0dqKjk2w8tZGmcyVK7d8jl4cvGcUjnNmnoWdOm\nhCQiUg+VVc7Vjy/h/4piJ0vt2DqHBy4dy8Du7dPQs6ZPCUlEJEHuzk+eWc5zy7fGlLXOyeKeaZos\n9bNQQhIRSdBv5q7h0Tc3xsSzs4w7vj6acYdpstTPosbhH2Hp8LpUhVVgRUSatZn/u447X40/WerN\n5w/nlKG9Utyj5qe28Yibw6O2b3NlA/0btUciIhnmicKN/Pq51XHL/uusoXx5dN+4ZVI/tSWkt8JK\nrzUys8WN3B8RkYwyd+VWrq1hstTvnjSIb5wwMMU9ar5qu4d0XALbJ1JHRKRJem3ddr7758XEmSuV\ni8b355pTh6S+U81YjQnJ3fdHvzezdmZWYGY9aqojItJcLCvexTdnFVJWGTtZ6lnDe3PDOZostbHV\nmJDM7Bwze9fMFpnZGcBK4A/AcjObVtN2B+3jXTNbbmZLzKwwxLqa2TwzWxueu4S4mdltZlZkZsvM\nbHTUfqaF+muj2zazMWH/RWFba2gbIiLVirZ9xCX3L2BPWWVM2ReG9OB3Xx2pyVKToLZLdr8AJgDf\nAp4ATnb38cBw4Pv1aONL7j4yauXAa4GX3H0w8FJ4D3A6MDg8ZgB3wsej/a4HxgFjgeurE0yoMyNq\nu4kNaUNEpNrmXfuYeu98dsSZLHV0/zzuumg0uTn6xkwy1PavWuXub7v7AuAdd18P4O7bgNg51hM3\nCZgVXs8CJkfFH/SIN4A8M+sNnAbMc/cd7r4TmAdMDGWd3P11j6zD/uBB+6pPGyIi7NhTxsX3zmdz\naezdiCN6deS+S46lXa4mS02W2hJSlpl1MbNuQFV43TWcsST654ED/zCzhWY2I8R6ufsWgPDcM8Tz\ngehvnBWHWG3x4jjxhrTxKWY2w8wKzaywpKQkwUMVkabsowMVXHL/m6wr2RNT1q9rWx6cPpa8dpos\nNZlqS/WdgYV88j2kRVFlccacxHW8u282s57APDOLP5A/It4FWW9AvDYJbePuM4GZAAUFBYkeq4g0\nUfvLK5nxYCHLiktjyrp3aM1D3xhHr06aLDXZakxI7j7gs+7c3TeH521m9jSRe0Dvm1lvd98SLpdt\nC9WLgX5Rm/cl8sXcYuDEg+KvhnjfOPVpQBsi0kKVVVRx1WOLeW3dBzFlHdvk8OA3xjJAk6WmRG2j\n7EbX9qhrx2bW3sw6Vr8mMkBiBTAHqB4pNw2YHV7PAaaGkXDjgdJwuW0uMCFcMuwS9jM3lO02s/Fh\ndN3Ug/ZVnzZEpAXaV1bJjIcKmbvy/Ziy1jlZ3HfJsQzt0ykNPWuZartkV0hkqHf1TZToy10OnFTH\nvnsBT4eR2DnAn939BTNbADxhZtOBDcBXQv3ngDOAImAvcCmAu+8ws18AC0K9n7v7jvD6cuABoC3w\nfHgA3FifNkSk5flwfzmXPVDIm+/uiCnLyTLuvGg0xw5IZEpPaSwWGaAWp8DsauA8oBR4DHja3WOX\nRmzmCgoKvLCwMN3dEJFGtGNPGVPvm8+KTR/GLb/1ayOZPCpmvJPUg5ktjPq6T0Jqm6nhFnc/AbiS\nyH2Xl8zsCTMb+Rn7KSKSNltL9/PVu1+Pm4yyDH5z/nAlozSpc0C9u79jZrOJXBa7GBgCLEl2x0RE\nGtu72/dw0b3zKd65L6asVbZx25RRnD5MX01Ml9rWQzoMmELky6QbiVy2+5XmrxORpmj11g+5+N43\nKdl9IKasTass7r64gC8O6RFnS0mV2s6QioBlREaofUhk3aPvVE8m6O6/S3rvREQaweINO7nk/gWU\n7iuPKevYOof7Lz2WAg1gSLvaEtLP+eRLox1S0BcRkUb3WtF2LnuwkL1xJkrt1j6XWd8YyzH5ndPQ\nMzlYbV+M/VkK+yEi0uj+sXIrVz66mLKK2CUkenduw8OXjePwHvp7O1PU9sXYGTWV1aeOiEg6PL24\nmMsfWRQ3GQ3s3p6/fPs4JaMMU9slu2vNbHst5QZcRZjzTUQkUzz0+rv8dPbKuGVHHtKRh6aPo0fH\n1qntlNSptoT0T+DsOraf14h9ERH5TNydP766jpvnrolbPrp/HvdfMpbO7VqluGeSiNruIWlaHRFp\nMtydG19Yzd3/XB+3/IRB3bn74jG0b631jDKVPhkRafIqq5yfzl7Bn+dviFt+2tG9uO2CUbTOyU5x\nz6Q+lJBEpEkrr6ziP59Yypyl8VeS+fLofH5z3nBysrXseKarMyGZWba7xw7gFxFJs/3llXznkUW8\nvHpb3PJLPjeA/zprKFlZ8dbmlEyTyJ8MRWZ2s5kNTXpvREQStHt/OdPue7PGZPQfJw3i+rOVjJqS\nRBLScOBt4B4ze8PMZpiZVqwSkbTZsaeMC++Zz/x3YtcyAvjxGUdxzYQjqJ7qTJqGOhOSu+929z+5\n++eAHwDXA1vMbJaZDaprezPLNrPFZvZseD/QzOab2Voze9zMckO8dXhfFMoHRO3juhBfY2anRcUn\nhliRmV0bFa93GyLSNGwt3c/X7n6dZcWlMWVmcOOXh/HNLxyWhp7JZ1VnQgoJ5Rwzexr4PfA/wGHA\n34iswFqXq4C3ot7fBNzi7oOBncD0EJ8O7HT3QcAtoR7hUuEU4GhgIvDH0Kds4A7gdGAocEHUZcV6\ntSEiTcOGD/bylbtfY+222LVCW2Ubt18wiilj+6ehZ9IYErlkt5bIEhQ3u/sod/+du7/v7k8CL9S2\noZn1Bc4E7gnvjcjS50+GKrOAyeH1pPCeUH5yqD8JeMzdD7j7O0RmIR8bHkXuvt7dy4gsjzGpgW2I\nSIZbs3U359/1Ght3xK5l1KZVFjOnFnDW8D5p6Jk0lloTUjgLecDdp7v7aweXu/t/1LH/W4lc5que\nTKobsMvdK8L7YqB6acZ8IusuEcpLQ/2P4wdtU1O8IW2ISAZbsnEXX5v5OtvirGXUsXUOD35jHF86\nomcaeiaNqdaEFIZ7f6khOzazs4Bt7r4wOhyvmTrKGiteV/sfCwM3Cs2ssKSkJM4mIpIqr6/7gAv/\n9Aa79sauZdS1fS6PzhjP2IFay6g5SOSLsa+Z2R+Ax4E91UF3X1THdscD55jZGUAboBORM6Y8M8sJ\nZyh9gepvsxUD/YBiM8sBOgM7ouLVoreJF9/egDY+xd1nEiaNLSgoiElYIpIaL731fo0zdh/SqQ0P\nXzaWQT07pqFnkgyJ3EP6HJEBBT8nMqDhf4Df1rWRu1/n7n3dfQCRQQkvu/uFwCvA+aHaNCIr0gLM\nCe8J5S+7u4f4lDBCbiAwGHgTWAAMDiPqckMbc8I29W1DRDLM7CWb+NZDC+Mmo0O7teMv3z5OyaiZ\nqfMMyd0bdMmuFj8EHjOzXwKLgXtD/F7gITMrInLWMiW0v9LMngBWARXAFdUzR5jZlcBcIBu4z91X\nNqQNEcksD7/xHj+dvYJ4fy4e0asjD00fS89ObVLfMUkqq+sEwcw6E/nu0RdC6J/Az9099ksAzVBB\nQYEXFhamuxsiLcadr67jphdWxy0b2S+PBy49lrx2uSnuldSXmS1094L6bJPIJbv7gN3AV8PjQ+D+\n+ndPRKRm7s5NL6yuMRl97vBuPHLZOCWjZiyRQQ2Hu/t5Ue9vMLMlyeqQiLQ8VWH5iEdqWD7i1KG9\nuP2CUbRppeUjmrNEzpD2mdkJ1W/M7Hgg9ptpIiINUF5ZxdVPLKkxGZ07Kp8/XjhayagFSOQM6XJg\nVriXZEQGA1ySzE6JSMuwv7ySK/+8iBffij9j99TjDuVnZx+tGbtbiERG2S0BRlTP8O3uHya9VyLS\n7G3bvZ/vPLyIwvd2xi2/8kuD+M8JQzRjdwuSyAJ9ecBUYACQU/3DkcC0QSIicS18byeXP7ww7lRA\nANedfiTf+uLhKe6VpFsil+yeA94AlvPJnHQiIvXm7vz5zQ38bM5Kyitjv3JiBr+aPIyvj9OM3S1R\nIgmpjbtfk/SeiEiztr+8kutnr+Txwo1xy3OyjN99bSTnjNCM3S1VIgnpITP7JvAs8PH5tbvHX6pR\nROQgm3ft4/JHFrF046645d075HLH10cz7jBNvt+SJZKQyoCbgR/zyczYTmSRPhGRWr2x/gOueGQR\nH+wpi1s+ol8ed100mt6d26a4Z5JpEklI1wCD3H17sjsjIs2Hu3P/v9/lV8+9RWVV/CnKphzbjxsm\nHU3rHH3HSBJLSCuBvcnuiIg0H/vKKrnuqWU8s2Rz3PJW2cYN5xyjwQvyKYkkpEpgiZm9wqfvIWnY\nt4jE2LhjL996aCGrtsT/ymKvTq2586IxjO7fJcU9k0yXSEJ6JjxERGr1r7UlfPfRxXFXdwUYO6Ar\nf7hwFD07aukIiZXITA2zzKwt0N/d16SgTyLSxLg7d/1zPTfPXU0Nt4u45HMD+PGZR9EqO5EpNKUl\nSmSmhrOJrBCbCww0s5FE1kM6J9mdE5HMt+dABf/vyaU8t3xr3PLWOVn8+txhnDemb4p7Jk1NIn+q\n/AwYC+yCj+e2G1jXRmbWxszeNLOlZrbSzG4I8YFmNt/M1prZ42H5ccIS5Y+bWVEoHxC1r+tCfI2Z\nnRYVnxhiRWZ2bVS83m2ISP29s30Pk+/4d43JKD+vLX+9/HNKRpKQRBJSRZzVYWtfZjbiAHCSu48A\nRgITzWw8cBNwi7sPBnYC00P96cBOdx8E3BLqYWZDiSw1fjQwEfijmWWbWTZwB3A6MBS4INSlvm2I\nSP299Nb7nPOH/2Ptto/ilh8/qBt/++4JHJPfOcU9k6YqkYS0wsy+DmSb2WAzux14ra6NPKL6J7VV\neDhwEvBkiM8CJofXk8J7QvnJFpnJdRLwmLsfcPd3gCIiZ2xjgSJ3X+/uZcBjwKSwTX3bEJEEVVU5\nt774NtNnFbJ7f0XcOt/6wmHMunQsXdtrdVdJXCIJ6btEzk4OAI8SWcL8e4nsPJzJLAG2AfOAdcAu\nd6/+KS4G8sPrfGAjQCgvBbpFxw/apqZ4twa0ISIJ+HB/OTMeKuTWF9fGLW/bKpvbLxjFdWccRY4G\nL0g9JTLKbi+RaYN+XN+du3slMDIsYfE0cFS8auE53pmK1xKP99NeW/3a2vgUM5sBzADo319f3BMB\nWPv+br710ELWb98Tt/zQbu24++IxHHlIpxT3TJqLREbZFQA/IqyHVB139+GJNuLuu8zsVWA8kGdm\nOeEMpS9Q/VXuYqAfUGxmOUBnIqvTVserRW8TL769AW0c3N+ZwEyAgoKCRO6XiTRrzy/fwvf/spQ9\nZZVxy790RA9u/dooOrdrleKeSXOSyDn1I8ADwHnA2VGPWplZj3BmRPge0ynAW8ArwPmh2jRgdng9\nJ7wnlL/s7h7iU8IIuYHAYOBNYAEwOIyoyyUy8GFO2Ka+bYhIHJVVzk0vrObyRxbVmIz+46RB3Dvt\nWCUj+cwSmamhxN3nNGDfvYFZYTRcFvCEuz9rZquAx8zsl8Bi4N5Q/14iS10UETlrmQLg7ivN7Alg\nFVABXBEuBWJmVwJzgWzgPndfGfb1w/q0ISKxdu0t47uPLuZfa+PPq9yhdQ7/89URnHb0ISnumTRX\nVtcJgpmdDFwAvMSn57J7KrldywwFBQVeWFiY7m6IpNSqzR/yrYcL2bhjX9zyw3u05+6LCxjUs0OK\neyZNhZktdPeC+myTyBnSpcCRRIZtVy9h7kCLSEgiLc3sJZv44V+Xsb+8Km75aUf34rdfGUHHNrpE\nJ40rkYQ0wt2HJb0nIpJW5ZVV/Pdzq7nv3+/ELTeD7084gsu/eDhZWfr6njS+RBLSG2Y21N1XJb03\nIpIW2z86wBWPLGL+OzGDTgHo1CaH318wii8d0TPFPZOWJJGEdAIwzczeIXIPyYhMxJDwsG8RyVxL\nN+7i2w8vZEvp/rjlRx7SkbsvHsOh3dqnuGfS0iSSkCYmvRcikhZPLNjIT2avoKwi/v2is0f04abz\nhtEuN5FfFSKfTSIzNbyXio6ISOocqKjkF8+u4uE3NsQtzzL40RlHMf2EgWi6R0kV/dkj0sIs2rCT\nHz65rMZZuru2z+UPF4zic4O6p7hn0tIpIYm0EHvLKviff7zNff9+h5q+fjgsvzN3XTyG/Ly2qe2c\nCEpIIi3Cv4u2c+1Ty2r8oivA+WP68svJx9CmVXYKeybyCSUkkWasdF85//3cWzy2YGONdXKyjOvP\nHspF4w/V/SJJKyUkkWbqHyu38pNnVrBt94Ea6wzL78xN5w1naB8tGSHpp4Qk0syU7D7Az/62kr8v\n21JjndY5WVx96hAuO2GgFtKTjKGEJNJMuDvPLNnEDX9bxa695TXWGzuwKzd+eRiH9dDEqJJZlJBE\nmoFNu/a6zjU3AAATnUlEQVTx46eX8+qakhrrdGidw7WnH8nXx/bXXHSSkZSQRJqwqirnkfnvcePz\nq2tcQA/gxCN68Otzh9FHw7klgykhiTRR60s+4tq/LufNd+NPiArQpV0rrj/7aCaN7KMRdJLxknY3\n08z6mdkrZvaWma00s6tCvKuZzTOzteG5S4ibmd1mZkVmtszMRkfta1qov9bMpkXFx5jZ8rDNbRb+\nxzWkDZGmoqKyijtfXcfE3/+r1mR09og+zLvmi0wela9kJE1CMofXVAD/6e5HAeOBK8xsKHAt8JK7\nDyayCu21of7pwODwmAHcCZHkAlwPjAPGAtdXJ5hQZ0bUdtUTwdarDZGmYtXmD5n8x39z0wura5wQ\ntVen1vxpagG3XzCK7h1ap7iHIg2XtEt27r4F2BJe7zazt4B8YBJwYqg2C3gV+GGIP+iRNdXfMLM8\nM+sd6s5z9x0AZjYPmGhmrwKd3P31EH8QmAw8X982Ql9FMtb+8kr+8HIRd/1zHRVVNcz7A1wwth/X\nnn4UndtqNVdpelJyD8nMBgCjgPlAr+oE4O5bzKx6xa98IPrr5MUhVlu8OE6cBrTxqYRkZjOInEHR\nv3//+h2sSCNb+N4OfvDkMtaV7KmxTv+u7bjxy8M0Iao0aUlPSGbWAfgr8D13/7CWa9nxCrwB8Vq7\nk8g27j4TmAlQUFBQ1z5FkmLPgQpunruGWa+/W+NkqFkG3zh+INdMGKI1i6TJS+pPsJm1IpKMHnH3\np0L4/erLZOGS3LYQLwb6RW3eF9gc4iceFH81xPvGqd+QNkQyyv++XcJ1Ty1n066aJ0Md0qsDN503\nnFH9u9RYR6QpSeYoOwPuBd5y999FFc0BqkfKTQNmR8WnhpFw44HScNltLjDBzLqEwQwTgLmhbLeZ\njQ9tTT1oX/VpQyQjlO4t5/t/WcrU+96sMRm1yjauOnkwz37380pG0qwk8wzpeOBiYLmZLQmxHwE3\nAk+Y2XRgA/CVUPYccAZQBOwFLgVw9x1m9gtgQaj38+oBDsDlwANAWyKDGZ4P8Xq1IZIJXlixhZ/O\nXklJLZOhjujbmZvOH86Rh2gyVGl+zGu6OC1A5B5SYWFhurshzdi23fu5fvZKnl+xtcY6bVpl8f0J\nR3Dp8QPJ1rQ/0gSY2UJ3L6jPNroLKpIm7s5fF23iF8+uonRfzZOhHndYN248bxiHdmufwt6JpJ4S\nkkgabNyxlx89vZx/rd1eY52OrXP40ZlHMeXYfpppQVoEJSSRFCqrqOKR+e9x89w17K1lMtRTjurJ\nLycP45DObVLYO5H0UkISSYHyyiqeWlTM7S8XUbyz5qHcXdvn8rNzjubs4b11ViQtjhKSSBJVVFbx\n9OJN3P5yERt27K217uSRffivs4+ma/vcFPVOJLMoIYkkQUVlFbOXbOb2l9fy7ge1J6Lendvwq3OP\n4aQje6WodyKZSQlJpBFVVjl/W7qZ215ay/rtNc89V+3Ccf259vQj6dhGk6GKKCGJNILKKufZZZFE\nVNskqNVOOrInV58yhGF9O6egdyJNgxKSyGdQVeU8t2ILv39xLWu3fVRn/ROP6MH3ThnCyH55Keid\nSNOihCTSAFVVztyVW7n1xbWseX93nfU/P7g7V586hNGae06kRkpIIvXg7sxd+T63vvg2q7fWnYiO\nH9SNq08ZQsGArinonUjTpoQkkgB358W3tnHri2+zcvOHddY/7rBuXH3qEMYOVCISSZQSkkgt3J1X\n1mzjlnlrWb6ptM76Ywd25epThnDc4d1S0DuR5kUJSSQOd+fVt0u49cW1LN24q876xw7o8nEi0gwL\nIg2jhCQSxd3519rt3PLi2yzeUHciGt0/j6tPHcIJg7orEYl8RkpIIkQS0b+LPuCWF99m4Xs766w/\nol8eV58ymC8O6aFEJNJIkrmE+X1mts3MVkTFuprZPDNbG567hLiZ2W1mVmRmy8xsdNQ200L9tWY2\nLSo+xsyWh21uC8uYN6gNadleX/cBX7v7DS66d36dyWh4387cf8mxPPOdz3HiET2VjEQaUdISEpGl\nxSceFLsWeMndBwMvhfcApwODw2MGcCdEkgtwPTAOGAtcX51gQp0ZUdtNbEgb0nLNX/8BU2a+zgV/\neoM3391Ra92j+3TinqkFzL7ieL50pBKRSDIk7ZKdu/+vmQ04KDwJODG8ngW8CvwwxB/0yHrqb5hZ\nnpn1DnXnufsOADObB0w0s1eBTu7+eog/CEwGnq9vG+6+pTGPWzLfgnd3cMu8t3lt3Qd11j2qdyeu\nPmUwpw7tpSQkkmSpvofUqzoBuPsWM+sZ4vnAxqh6xSFWW7w4TrwhbcQkJDObQeQsiv79+9fzECUT\nVVY5b6z/gLv+ua7WVVqrHXlIR753ymAmDD2ErCwlIpFUyJRBDfH+x3sD4g1pIzboPhOYCVBQUFDX\nfiWDrd76IU8v3sTsxZvZ+uH+OusP6dWBq04ewunHKBGJpFqqE9L71ZfJwiW5bSFeDPSLqtcX2Bzi\nJx4UfzXE+8ap35A2pJnZWrqfOUs38dSiTQlN7wMwqGcHrjp5MGcO661EJJImqU5Ic4BpwI3heXZU\n/Eoze4zIAIbSkFDmAr+OGsgwAbjO3XeY2W4zGw/MB6YCtzekjSQeq6TQRwcqeGHFVp5ZvIl/r9uO\nJ3hee1iP9lx18mDOGt6HbCUikbRKWkIys0eJnN10N7NiIqPlbgSeMLPpwAbgK6H6c8AZQBGwF7gU\nICSeXwALQr2fVw9wAC4nMpKvLZHBDM+HeL3akKarvLKK/1u7nacXb+Ifq7ayv7wq4W0HdGvHVacM\n5pwR+UpEIhnCPNE/JVuogoICLywsTHc3JHB3lhWX8vTiTfxt6WY+2FOW8LY5WcYXh/Tg3NH5TDz6\nEHKyk/mtB5GWzcwWuntBfbbJlEENIrXauGMvzyzexNNLNrE+gRVZo43sl8e5o/I5a3hvunVonaQe\nishnpYQkGWvX3jL+vnwLzyzexIJ3657OJ1r/ru2YPCqfc0flM7B7+yT1UEQakxKSZJQDFZW8snob\nTy/exCurSyirTPy+UF67Vpw1vDfnjurL6P55+iKrSBOjhCRpV1XlFL63k6cXb+Lvyzbz4f6KhLfN\nzcnilKN6MnlkPice0ZPcHN0XEmmqlJAkbYq2fcQzizfxzJJNFO/cV69txw3syrmj8jl9WG86t22V\npB6KSCopIUlKlew+wN+WbubpxZsSWoE12qCeHTh3VD6TRvahb5d2SeqhiKSLEpIk3bYP9/Paug94\nZskm/rV2O5VViX/VoHuH1kwa2YdzR+VzdJ9Oui8k0owpIUmj2l9eyYpNpSzesIslG3exeMNONpfW\nPYdctLatspl4zCFMHpXP8Yd30/eFRFoIJSRpMHfnne17QuKJJKC3tnxIRT3OgKplGZwwuAfnjurD\nhKGH0L61fjRFWhr9r5eE7dpb9qnks2TjLkr3lX+mfR6T34nJI/M5Z0QfenZq00g9FZGmSAlJ4iqv\nrGL1lt0s3riTJRt2sXjjLt7ZXr8ZEmqSn9f24/tCg3t1bJR9ikjTp4QkuDubS/dHEs+GnSzZuIvl\nm0o5UJH4l1Jrk51lHHlIR8Yc2oUzhvVm7ICuWuJBRGIoIbVAew5UsKy49FNnPyW7DzTa/nt3bsOo\n/nmM7JfHyH5dGJbfmba52Y22fxFpnpSQmrmqKqeo5KOPz3wWb9jF2+/vpgHjDuJq2yqb4X07M7J/\nHqNCAjqks+4FiUj9KSE1Ee7OnrJKdu4po3RfObv2lrNzbxm79pWza0/keefeMkqj43vLKd1XXq/v\n/dRlUM8OkcTTP49R/bowpFcHDcsWkUbR4hKSmU0Efg9kA/e4+42pbN/d2Vde+XFCiSSQcnbtK2PX\n3nJ27S0LZeWU7iuLlIXX5ZWpXbuqa/vccNaTx6j+XRjerzOd2miaHhFJjhaVkMwsG7gDOBUoBhaY\n2Rx3X9VYbawr+Yh/rHw/kmD2RBLNzr3lnzpzKWukwQKNKTc7i6F9OoXkEzn76de1rWZGEJGUaVEJ\nCRgLFLn7egAzewyYBDRaQlr7/kfc9MLqxtpd0vTv2i4MOogkoKF9OtE6RwMPRCR9WlpCygc2Rr0v\nBsY1ZgN57TLvklanNjkM7/tJ8hnRL4/uWjlVRDJMS0tI8a4/xdyYMbMZwAyA/v3716uBLu1yG9Sx\nRLTOyaJLu1zy2rWKPNrm0qV9Kzq3zaVLdaxdLnltW9GlfeS5c7tWOvMRkSahpSWkYqBf1Pu+wOaD\nK7n7TGAmQEFBQb1GEiRyhtQq28hrF5JI208STJd2uXQOz3ltQ3KJKmvTSolFRJqvlpaQFgCDzWwg\nsAmYAny9MRvIa9eKy04Y+MnZSnWiiTpraZebrcECIiIHaVEJyd0rzOxKYC6RYd/3ufvKxmyjdU42\nPzlraGPuUkSkRWhRCQnA3Z8Dnkt3P0RE5NP0FXsREckISkgiIpIRlJBERCQjKCGJiEhGUEISEZGM\nYO6pnUG6qTGzEuC9Bm7eHdjeiN1pCnTMLYOOuWX4LMd8qLv3qM8GSkhJZGaF7l6Q7n6kko65ZdAx\ntwypPmZdshMRkYyghCQiIhlBCSm5Zqa7A2mgY24ZdMwtQ0qPWfeQREQkI+gMSUREMoISUpKY2UQz\nW2NmRWZ2bbr7Uxcz62dmr5jZW2a20syuCvGuZjbPzNaG5y4hbmZ2Wzi+ZWY2Ompf00L9tWY2LSo+\nxsyWh21us7AGR01tpPDYs81ssZk9G94PNLP5oT+Pm1luiLcO74tC+YCofVwX4mvM7LSoeNyfg5ra\nSNHx5pnZk2a2OnzexzX3z9nMrg4/1yvM7FEza9PcPmczu8/MtpnZiqhY2j7X2tqokbvr0cgPIktb\nrAMOA3KBpcDQdPerjj73BkaH1x2Bt4GhwG+Aa0P8WuCm8PoM4Hkiq/COB+aHeFdgfXjuEl53CWVv\nAseFbZ4HTg/xuG2k8NivAf4MPBvePwFMCa/vAi4Pr78D3BVeTwEeD6+Hhs+4NTAwfPbZtf0c1NRG\nio53FnBZeJ0L5DXnzxnIB94B2kb921/S3D5n4AvAaGBFVCxtn2tNbdR6DKn6T9CSHuFDmxv1/jrg\nunT3q57HMBs4FVgD9A6x3sCa8Ppu4IKo+mtC+QXA3VHxu0OsN7A6Kv5xvZraSNFx9gVeAk4Cng3/\nebYDOQd/lkTW0TouvM4J9ezgz7e6Xk0/B7W1kYLj7UTkl7MdFG+2nzORhLQx/JLNCZ/zac3xcwYG\n8OmElLbPtaY2auu/LtklR/V/gGrFIdYkhEsUo4D5QC933wIQnnuGajUdY23x4jhxamkjFW4FfgBU\nhffdgF3uXhGnnx8fWygvDfXr+29RWxvJdhhQAtxvkcuU95hZe5rx5+zum4DfAhuALUQ+t4U078+5\nWjo/13r/HlRCSo5465M3ieGMZtYB+CvwPXf/sLaqcWLegHjamNlZwDZ3XxgdjlPV6yhrSv8WOUQu\n69zp7qOAPUQus9SkKR1bXOGexiQil9n6AO2B0+NUbU6fc11ScSz13kYJKTmKgX5R7/sCm9PUl4SZ\nWSsiyegRd38qhN83s96hvDewLcRrOsba4n3jxGtrI9mOB84xs3eBx4hctrsVyDOz6tWUo/v58bGF\n8s7ADur/b7G9ljaSrRgodvf54f2TRBJUc/6cTwHecfcSdy8HngI+R/P+nKul83Ot9+9BJaTkWAAM\nDiNsconcGJ2T5j7VKoyYuRd4y91/F1U0B6geaTONyL2l6vjUMJJmPFAaTtfnAhPMrEv4y3QCkevm\nW4DdZjY+tDX1oH3FayOp3P06d+/r7gOIfEYvu/uFwCvA+XH6E93P80N9D/EpYXTWQGAwkRvAcX8O\nwjY1tZFU7r4V2GhmR4TQycAqmvHnTORS3Xgzaxf6VH3MzfZzjpLOz7WmNmqWipuKLfFBZITJ20RG\n3/w43f1JoL8nEDmdXgYsCY8ziFwHfwlYG567hvoG3BGObzlQELWvbwBF4XFpVLwAWBG2+QOffDE7\nbhspPv4T+WSU3WFEftEUAX8BWod4m/C+KJQfFrX9j8NxrSGMPqrt56CmNlJ0rCOBwvBZP0NkNFWz\n/pyBG4DVoV8PERkp16w+Z+BRIvfIyomcnUxP5+daWxs1PTRTg4iIZARdshMRkYyghCQiIhlBCUlE\nRDKCEpKIiGQEJSQREckISkgiGSpM6zM03f0QSRUN+xYRkYygMySRNDOz9mb2dzNbapH1er4W4q+a\nWYGZnWNmS8JjjZm9E8rHmNk/zWyhmc2tnr7loH0/ENakec3M1pvZ+QfXEckUOXVXEZEkmwhsdvcz\nAcysc3Shu88hTD1lZk8A/wzzDt4OTHL3kpDEfkXkW/YH601kJo4jw36eTNaBiHwWSkgi6bcc+K2Z\n3URk+qJ/xatkZj8A9rn7HWZ2DHAMMC8s3JlNZNqYeJ5x9ypglZn1avzuizQOJSSRNHP3t81sDJH5\n0P7bzP7h7j+PrmNmJwNfIbIqKETmCVvp7scl0MSB6F01Rp9FkkH3kETSzMz6AHvd/WEiC8mNPqj8\nUOCPwFfdfV8IrwF6mNlxoU4rMzs6hd0WaXQ6QxJJv2HAzWZWRWSm5ssPKr+EyIzKT4fLc5vd/Yww\nQOG2cM8ph8haTitT1muRRqZh3yIikhF0yU5ERDKCEpKIiGQEJSQREckISkgiIpIRlJBERCQjKCGJ\niEhGUEISEZGMoIQkIiIZ4f8DhKkk950sfbcAAAAASUVORK5CYII=\n",
      "text/plain": [
       "<matplotlib.figure.Figure at 0x1121c14a8>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "import numpy as np\n",
    "import matplotlib.pyplot as plt\n",
    "\n",
    "x = np.linspace(0, 1e6, 10)\n",
    "plt.plot(x, 8.0 * (x**2) / 1e6, lw=5)   \n",
    "plt.xlabel('size n')\n",
    "plt.ylabel('memory [MB]')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2.5.1.2 稀疏矩阵 vs. 稀疏矩阵存储方案\n",
    "\n",
    "- 稀疏矩阵是一个矩阵，绝大多数是空的\n",
    "- 存储所有的0是浪费 -> 只存储非0项目\n",
    "- 想一下**压缩**\n",
    "- 有利: 巨大的内存节省\n",
    "- 不利: 依赖实际的存储方案, (\\*) 通常并不能满足\n",
    "\n",
    "### 2.5.1.3 典型应用\n",
    "- 偏微分方程（PDES）的解\n",
    "    - 有限元素法\n",
    "    - 机械工程、电子、物理...\n",
    "- 图论\n",
    "    - （i，j）不是0表示节点i与节点j是联接的\n",
    "- ...\n",
    "\n",
    "### 2.5.1.4 先决条件\n",
    "\n",
    "最新版本的\n",
    "- `numpy`\n",
    "- `scipy`\n",
    "- `matplotlib` (可选)\n",
    "- `ipython` (那些增强很方便)\n",
    "\n",
    "### 2.5.1.5 稀疏结构可视化\n",
    "\n",
    "- matplotlib中的`spy()`\n",
    "- 样例绘图:\n",
    "\n",
    "![](http://www.scipy-lectures.org/_images/graph.png)\n",
    "![](http://www.scipy-lectures.org/_images/graph_g.png)\n",
    "![](http://www.scipy-lectures.org/_images/graph_rcm.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2.5.2 存储机制\n",
    "\n",
    "- scipy.sparse中有七类稀疏矩阵:\n",
    "    1. csc_matrix: 压缩列格式\n",
    "    2. csr_matrix: 压缩行格式\n",
    "    3. bsr_matrix: 块压缩行格式\n",
    "    4. lil_matrix: 列表的列表格式\n",
    "    5. dok_matrix: 值的字典格式\n",
    "    6. coo_matrix: 座标格式 (即 IJV, 三维格式)\n",
    "    7. dia_matrix: 对角线格式\n",
    "- 每一个类型适用于一些任务\n",
    "- 许多都利用了由Nathan Bell提供的稀疏工具 C++ 模块\n",
    "- 假设导入了下列模块:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import scipy.sparse as sparse\n",
    "import matplotlib.pyplot as plt"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- 给Numpy用户的**warning**:\n",
    "    - 使用'\\*'的乘是*矩阵相乘* (点积)\n",
    "    - 并不是Numpy的一部分!\n",
    "        - 向Numpy函数传递一个稀疏矩阵希望一个ndarray/矩阵是没用的"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2.5.2.1 通用方法\n",
    "\n",
    "- 所有scipy.sparse类都是spmatrix的子类\n",
    "    - 算术操作的默认实现\n",
    "        - 通常转化为CSR\n",
    "        - 为了效率而子类覆盖\n",
    "    - 形状、数据类型设置/获取\n",
    "    - 非0索引\n",
    "    - 格式转化、与Numpy交互(toarray(), todense())\n",
    "    - ...\n",
    "\n",
    "- 属性:\n",
    "    - mtx.A - 与mtx.toarray()相同\n",
    "    - mtx.T - 转置 (与mtx.transpose()相同)\n",
    "    - mtx.H - Hermitian (列举) 转置\n",
    "    - mtx.real - 复矩阵的真部\n",
    "    - mtx.imag - 复矩阵的虚部\n",
    "    - mtx.size - 非零数 (与self.getnnz()相同)\n",
    "    - mtx.shape - 行数和列数 (元组)\n",
    "\n",
    "- 数据通常储存在Numpy数组中\n",
    "\n",
    "### 2.5.2.2 稀疏矩阵类\n",
    "#### 2.5.2.2.1 对角线格式 (DIA)\n",
    "- 非常简单的格式\n",
    "- 形状 (n_diag, length) 的密集Numpy数组的对角线\n",
    "    - 固定长度 -> 当离主对角线比较远时会浪费空间\n",
    "    - \\_data_matrix的子类 (带数据属性的稀疏矩阵类)\n",
    "- 每个对角线的偏移\n",
    "    - 0 是主对角线\n",
    "    - 负偏移 = 下面\n",
    "    - 正偏移 = 上面\n",
    "- 快速矩阵 * 向量 (sparsetools)\n",
    "- 快速方便的关于项目的操作\n",
    "    - 直接操作数据数组 (快速的NumPy机件)\n",
    "- 构建器接受 :\n",
    "    - 密集矩阵 (数组)\n",
    "    - 稀疏矩阵\n",
    "    - 形状元组 (创建空矩阵)\n",
    "    - (数据, 偏移) 元组\n",
    "- 没有切片、没有单个项目访问\n",
    "- 用法 :\n",
    "    - 非常专业\n",
    "    - 通过有限微分解偏微分方程\n",
    "    - 有一个迭代求解器\n",
    "    \n",
    "##### 2.5.2.2.1.1 示例\n",
    "- 创建一些DIA矩阵 :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[1, 2, 3, 4],\n",
       "       [1, 2, 3, 4],\n",
       "       [1, 2, 3, 4]])"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "data = np.array([[1, 2, 3, 4]]).repeat(3, axis=0)\n",
    "data"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<4x4 sparse matrix of type '<class 'numpy.int64'>'\n",
       "\twith 9 stored elements (3 diagonals) in DIAgonal format>"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "offsets = np.array([0, -1, 2])\n",
    "mtx = sparse.dia_matrix((data, offsets), shape=(4, 4))\n",
    "mtx "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "matrix([[1, 0, 3, 0],\n",
       "        [1, 2, 0, 4],\n",
       "        [0, 2, 3, 0],\n",
       "        [0, 0, 3, 4]])"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mtx.todense()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[ 1,  2,  3,  4],\n",
       "       [ 5,  6,  7,  8],\n",
       "       [ 9, 10, 11, 12]])"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "data = np.arange(12).reshape((3, 4)) + 1\n",
    "data"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[ 1,  2,  3,  4],\n",
       "       [ 5,  6,  7,  8],\n",
       "       [ 9, 10, 11, 12]])"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mtx = sparse.dia_matrix((data, offsets), shape=(4, 4))\n",
    "mtx.data"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([ 0, -1,  2], dtype=int32)"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mtx.offsets"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "  (0, 0)\t1\n",
      "  (1, 1)\t2\n",
      "  (2, 2)\t3\n",
      "  (3, 3)\t4\n",
      "  (1, 0)\t5\n",
      "  (2, 1)\t6\n",
      "  (3, 2)\t7\n",
      "  (0, 2)\t11\n",
      "  (1, 3)\t12\n"
     ]
    }
   ],
   "source": [
    "print(mtx)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "matrix([[ 1,  0, 11,  0],\n",
       "        [ 5,  2,  0, 12],\n",
       "        [ 0,  6,  3,  0],\n",
       "        [ 0,  0,  7,  4]])"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mtx.todense()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- 机制的解释 :\n",
    "\n",
    "偏移: 行\n",
    "\n",
    "     2:  9\n",
    "     1:  --10------\n",
    "     0:  1  . 11  .\n",
    "    -1:  5  2  . 12\n",
    "    -2:  .  6  3  .\n",
    "    -3:  .  .  7  4\n",
    "         ---------8\n",
    "         \n",
    "- 矩阵-向量相乘"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([ 1.,  1.,  1.,  1.])"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "vec = np.ones((4, ))\n",
    "vec"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([ 12.,  19.,   9.,  11.])"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mtx * vec"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[  1.,   0.,  11.,   0.],\n",
       "       [  5.,   2.,   0.,  12.],\n",
       "       [  0.,   6.,   3.,   0.],\n",
       "       [  0.,   0.,   7.,   4.]])"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mtx.toarray() * vec"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 2.5.2.2.2 列表的列表格式 (LIL)\n",
    "- 基于行的联接列表\n",
    "    - 每一行是一个Python列表（排序的）非零元素的列索引\n",
    "    - 行存储在Numpy数组中 (dtype=np.object)\n",
    "    - 非零值也近似存储\n",
    "- 高效增量构建稀疏矩阵\n",
    "- 构建器接受 :\n",
    "    - 密集矩阵 (数组)\n",
    "    - 稀疏矩阵\n",
    "    - 形状元组 (创建一个空矩阵)\n",
    "- 灵活切片、高效改变稀疏结构\n",
    "- 由于是基于行的，算术和行切片慢\n",
    "- 用途 :\n",
    "    - 当稀疏模式并不是已知的逻辑或改变\n",
    "    - 例子：从一个文本文件读取稀疏矩阵\n",
    "\n",
    "##### 2.5.2.2.2.1 示例\n",
    "- 创建一个空的LIL矩阵 :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "mtx = sparse.lil_matrix((4, 5))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- 准备随机数据:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[ 1.,  1.,  1.],\n",
       "       [ 0.,  1.,  1.]])"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from numpy.random import rand\n",
    "data = np.round(rand(2, 3))\n",
    "data"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- 使用象征所以分配数据:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<4x5 sparse matrix of type '<class 'numpy.float64'>'\n",
       "\twith 5 stored elements in LInked List format>"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mtx[:2, [1, 2, 3]] = data\n",
    "mtx  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "  (0, 1)\t1.0\n",
      "  (0, 2)\t1.0\n",
      "  (0, 3)\t1.0\n",
      "  (1, 2)\t1.0\n",
      "  (1, 3)\t1.0\n"
     ]
    }
   ],
   "source": [
    "print(mtx)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "matrix([[ 0.,  1.,  1.,  1.,  0.],\n",
       "        [ 0.,  0.,  1.,  1.,  0.],\n",
       "        [ 0.,  0.,  0.,  0.,  0.],\n",
       "        [ 0.,  0.,  0.,  0.,  0.]])"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mtx.todense()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[ 0.,  1.,  1.,  1.,  0.],\n",
       "       [ 0.,  0.,  1.,  1.,  0.],\n",
       "       [ 0.,  0.,  0.,  0.,  0.],\n",
       "       [ 0.,  0.,  0.,  0.,  0.]])"
      ]
     },
     "execution_count": 23,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mtx.toarray()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "更多的切片和索引:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "matrix([[0, 1, 2, 0],\n",
       "        [3, 0, 1, 0],\n",
       "        [1, 0, 0, 1]], dtype=int64)"
      ]
     },
     "execution_count": 24,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mtx = sparse.lil_matrix([[0, 1, 2, 0], [3, 0, 1, 0], [1, 0, 0, 1]])\n",
    "mtx.todense()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "  (0, 1)\t1\n",
      "  (0, 2)\t2\n",
      "  (1, 0)\t3\n",
      "  (1, 2)\t1\n",
      "  (2, 0)\t1\n",
      "  (2, 3)\t1\n"
     ]
    }
   ],
   "source": [
    "print(mtx)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<2x4 sparse matrix of type '<class 'numpy.int64'>'\n",
       "\twith 4 stored elements in LInked List format>"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mtx[:2, :] "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "matrix([[0, 1, 2, 0],\n",
       "        [3, 0, 1, 0]], dtype=int64)"
      ]
     },
     "execution_count": 27,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mtx[:2, :].todense()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "matrix([[3, 1]], dtype=int64)"
      ]
     },
     "execution_count": 28,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mtx[1:2, [0,2]].todense()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "matrix([[0, 1, 2, 0],\n",
       "        [3, 0, 1, 0],\n",
       "        [1, 0, 0, 1]], dtype=int64)"
      ]
     },
     "execution_count": 29,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mtx.todense()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 2.5.2.2.3 值的字典格式 (DOK)\n",
    "\n",
    "- Python字典的子类\n",
    "    - 键是 (行, 列) 索引元组 (不允许重复的条目)\n",
    "    - 值是对应的非零值\n",
    "- 高效增量构建稀疏矩阵\n",
    "- 构建器支持:\n",
    "    - 密集矩阵 (数组)\n",
    "    - 稀疏矩阵\n",
    "    - 形状元组 (创建空矩阵)\n",
    "- 高效 O(1) 对单个元素的访问\n",
    "- 灵活索引，改变稀疏结构是高效\n",
    "- 一旦创建完成后可以被高效转换为coo_matrix\n",
    "- 算术很慢 (循环用`dict.iteritems()`)\n",
    "- 用法:\n",
    "    - 当稀疏模式是未知的假设或改变时\n",
    "    \n",
    "##### 2.5.2.2.3.1 示例\n",
    "\n",
    "- 逐个元素创建一个DOK矩阵:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<5x5 sparse matrix of type '<class 'numpy.float64'>'\n",
       "\twith 0 stored elements in Dictionary Of Keys format>"
      ]
     },
     "execution_count": 30,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mtx = sparse.dok_matrix((5, 5), dtype=np.float64)\n",
    "mtx"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<5x5 sparse matrix of type '<class 'numpy.float64'>'\n",
       "\twith 20 stored elements in Dictionary Of Keys format>"
      ]
     },
     "execution_count": 31,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "for ir in range(5):\n",
    "    for ic in range(5):\n",
    "        mtx[ir, ic] = 1.0 * (ir != ic)\n",
    "mtx"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "matrix([[ 0.,  1.,  1.,  1.,  1.],\n",
       "        [ 1.,  0.,  1.,  1.,  1.],\n",
       "        [ 1.,  1.,  0.,  1.,  1.],\n",
       "        [ 1.,  1.,  1.,  0.,  1.],\n",
       "        [ 1.,  1.,  1.,  1.,  0.]])"
      ]
     },
     "execution_count": 32,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mtx.todense()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- 切片与索引:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.0"
      ]
     },
     "execution_count": 33,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mtx[1, 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<1x2 sparse matrix of type '<class 'numpy.float64'>'\n",
       "\twith 1 stored elements in Dictionary Of Keys format>"
      ]
     },
     "execution_count": 34,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mtx[1, 1:3]     "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "matrix([[ 0.,  1.]])"
      ]
     },
     "execution_count": 35,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mtx[1, 1:3].todense()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "matrix([[ 1.,  0.],\n",
       "        [ 0.,  1.]])"
      ]
     },
     "execution_count": 36,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mtx[[2,1], 1:3].todense() "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 2.5.2.2.4 座标格式 (COO)\n",
    "\n",
    "- 也被称为 ‘ijv’ 或 ‘triplet’ 格式\n",
    "    - 三个NumPy数组: row, col, data\n",
    "    - `data[i]`是在 (row[i], col[i]) 位置的值\n",
    "    - 允许重复值\n",
    "- `_data_matrix`的子类 (带有`data`属性的稀疏矩阵类)\n",
    "- 构建稀疏矩阵的高速模式\n",
    "- 构建器接受:\n",
    "    - 密集矩阵 (数组)\n",
    "    - 稀疏矩阵\n",
    "    - 形状元组 (创建空数组)\n",
    "    - `(data, ij)`元组\n",
    "- 与CSR/CSC格式非常快的互相转换\n",
    "- 快速的矩阵 * 向量 (sparsetools)\n",
    "- 快速而简便的逐项操作\n",
    "    - 直接操作数据数组 (快速NumPy机制)\n",
    "- 没有切片，没有算术 (直接)\n",
    "- 使用:\n",
    "    - 在各种稀疏格式间的灵活转换\n",
    "    - 当转化到其他形式 (通常是 CSR 或 CSC), 重复的条目被加总到一起\n",
    "        - 有限元素矩阵的快速高效创建\n",
    "        \n",
    "##### 2.5.2.2.4.1 示例\n",
    "\n",
    "- 创建空的COO矩阵:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "matrix([[0, 0, 0, 0],\n",
       "        [0, 0, 0, 0],\n",
       "        [0, 0, 0, 0]], dtype=int8)"
      ]
     },
     "execution_count": 37,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mtx = sparse.coo_matrix((3, 4), dtype=np.int8)\n",
    "mtx.todense()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- 用 (data, ij) 元组创建:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<4x4 sparse matrix of type '<class 'numpy.int64'>'\n",
       "\twith 4 stored elements in COOrdinate format>"
      ]
     },
     "execution_count": 38,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "row = np.array([0, 3, 1, 0])\n",
    "col = np.array([0, 3, 1, 2])\n",
    "data = np.array([4, 5, 7, 9])\n",
    "mtx = sparse.coo_matrix((data, (row, col)), shape=(4, 4))\n",
    "mtx     "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "matrix([[4, 0, 9, 0],\n",
       "        [0, 7, 0, 0],\n",
       "        [0, 0, 0, 0],\n",
       "        [0, 0, 0, 5]])"
      ]
     },
     "execution_count": 39,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mtx.todense()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 2.5.2.2.5 压缩稀疏行格式 (CSR)\n",
    "- 面向行\n",
    "    - 三个Numpy数组: `indices`, `indptr`, `data`\n",
    "        - `indices`是列索引的数组\n",
    "        - `data`是对应的非零值数组\n",
    "        - `indptr`指向行开始的所以和数据\n",
    "        - 长度是`n_row + 1`, 最后一个项目 = 值数量 = `indices`和`data`的长度\n",
    "        - i-th行的非零值是列索引为`indices[indptr[i]:indptr[i+1]]`的`data[indptr[i]:indptr[i+1]]`\n",
    "        - 项目 (i, j) 可以通过`data[indptr[i]+k]`, k是j在`indices[indptr[i]:indptr[i+1]]`的位置来访问\n",
    "    - `_cs_matrix` (常规 CSR/CSC 功能) 的子类\n",
    "    - `_data_matrix` (带有`data`属性的稀疏矩阵类) 的子类\n",
    "- 快速矩阵向量相乘和其他算术 (sparsetools)\n",
    "- 构建器接受:\n",
    "    - 密集矩阵 (数组)\n",
    "    - 稀疏矩阵\n",
    "    - 形状元组 (创建空矩阵)\n",
    "    - `(data, ij)` 元组\n",
    "    - `(data, indices, indptr)` 元组\n",
    "- 高效行切片，面向行的操作\n",
    "- 较慢的列切片，改变稀疏结构代价昂贵\n",
    "- 用途:\n",
    "    - 实际计算 (大多数线性求解器都支持这个格式)\n",
    "\n",
    "##### 2.5.2.2.5.1 示例\n",
    "\n",
    "- 创建空的CSR矩阵:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "matrix([[0, 0, 0, 0],\n",
       "        [0, 0, 0, 0],\n",
       "        [0, 0, 0, 0]], dtype=int8)"
      ]
     },
     "execution_count": 40,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mtx = sparse.csr_matrix((3, 4), dtype=np.int8)\n",
    "mtx.todense()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- 用`(data, ij)`元组创建:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<3x3 sparse matrix of type '<class 'numpy.int64'>'\n",
       "\twith 6 stored elements in Compressed Sparse Row format>"
      ]
     },
     "execution_count": 41,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "row = np.array([0, 0, 1, 2, 2, 2])\n",
    "col = np.array([0, 2, 2, 0, 1, 2])\n",
    "data = np.array([1, 2, 3, 4, 5, 6])\n",
    "mtx = sparse.csr_matrix((data, (row, col)), shape=(3, 3))\n",
    "mtx     "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "matrix([[1, 0, 2],\n",
       "        [0, 0, 3],\n",
       "        [4, 5, 6]], dtype=int64)"
      ]
     },
     "execution_count": 42,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mtx.todense()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([1, 2, 3, 4, 5, 6], dtype=int64)"
      ]
     },
     "execution_count": 43,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mtx.data"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([0, 2, 2, 0, 1, 2], dtype=int32)"
      ]
     },
     "execution_count": 44,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mtx.indices"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([0, 2, 3, 6], dtype=int32)"
      ]
     },
     "execution_count": 45,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mtx.indptr"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "用`(data, indices, indptr)`元组创建:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "matrix([[1, 0, 2],\n",
       "        [0, 0, 3],\n",
       "        [4, 5, 6]])"
      ]
     },
     "execution_count": 46,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "data = np.array([1, 2, 3, 4, 5, 6])\n",
    "indices = np.array([0, 2, 2, 0, 1, 2])\n",
    "indptr = np.array([0, 2, 3, 6])\n",
    "mtx = sparse.csr_matrix((data, indices, indptr), shape=(3, 3))\n",
    "mtx.todense()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 2.5.2.2.6 压缩稀疏列格式 (CSC)\n",
    "\n",
    "- 面向列\n",
    "    - 三个Numpy数组: `indices`、`indptr`、`data`\n",
    "    - `indices`是行索引的数组\n",
    "    - `data`是对应的非零值\n",
    "    - `indptr`指向`indices`和`data`开始的列\n",
    "    - 长度是`n_col + 1`, 最后一个条目 = 值数量 = `indices`和`data`的长度\n",
    "    - 第i列的非零值是行索引为`indices[indptr[i]:indptr[i+1]]`的`data[indptr[i]:indptr[i+1]]`\n",
    "    - 项目 (i, j) 可以作为`data[indptr[j]+k]`访问, k是i在`indices[indptr[j]:indptr[j+1]]`的位置\n",
    "    - `_cs_matrix`的子类 (通用的 CSR/CSC 功能性)\n",
    "        - `_data_matrix`的子类 (带有`data`属性的稀疏矩阵类)\n",
    "- 快速的矩阵和向量相乘及其他数学 (sparsetools)\n",
    "- 构建器接受：\n",
    "    - 密集矩阵 (数组)\n",
    "    - 稀疏矩阵\n",
    "    - 形状元组 (创建空矩阵)\n",
    "    - `(data, ij)`元组\n",
    "    - `(data, indices, indptr)`元组\n",
    "- 高效列切片、面向列的操作\n",
    "- 较慢的行切片、改变稀疏结构代价昂贵\n",
    "- 用途:\n",
    "    - 实际计算 (巨大多数线性求解器支持这个格式)\n",
    "    \n",
    "##### 2.5.2.2.6.1 示例\n",
    "\n",
    "- 创建空CSC矩阵:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "matrix([[0, 0, 0, 0],\n",
       "        [0, 0, 0, 0],\n",
       "        [0, 0, 0, 0]], dtype=int8)"
      ]
     },
     "execution_count": 47,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mtx = sparse.csc_matrix((3, 4), dtype=np.int8)\n",
    "mtx.todense()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- 用`(data, ij)`元组创建:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<3x3 sparse matrix of type '<class 'numpy.int64'>'\n",
       "\twith 6 stored elements in Compressed Sparse Column format>"
      ]
     },
     "execution_count": 48,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "row = np.array([0, 0, 1, 2, 2, 2])\n",
    "col = np.array([0, 2, 2, 0, 1, 2])\n",
    "data = np.array([1, 2, 3, 4, 5, 6])\n",
    "mtx = sparse.csc_matrix((data, (row, col)), shape=(3, 3))\n",
    "mtx     "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "matrix([[1, 0, 2],\n",
       "        [0, 0, 3],\n",
       "        [4, 5, 6]], dtype=int64)"
      ]
     },
     "execution_count": 49,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mtx.todense()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([1, 4, 5, 2, 3, 6], dtype=int64)"
      ]
     },
     "execution_count": 50,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mtx.data"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([0, 2, 2, 0, 1, 2], dtype=int32)"
      ]
     },
     "execution_count": 51,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mtx.indices"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([0, 2, 3, 6], dtype=int32)"
      ]
     },
     "execution_count": 52,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mtx.indptr"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- 用`(data, indices, indptr)`元组创建:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "matrix([[1, 0, 2],\n",
       "        [0, 0, 3],\n",
       "        [4, 5, 6]])"
      ]
     },
     "execution_count": 53,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "data = np.array([1, 4, 5, 2, 3, 6])\n",
    "indices = np.array([0, 2, 2, 0, 1, 2])\n",
    "indptr = np.array([0, 2, 3, 6])\n",
    "mtx = sparse.csc_matrix((data, indices, indptr), shape=(3, 3))\n",
    "mtx.todense()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 2.5.2.2.7 块压缩行格式 (BSR)\n",
    "- 本质上，CSR带有密集的固定形状的子矩阵而不是纯量的项目\n",
    "    - 块大小`(R, C)`必须可以整除矩阵的形状`(M, N)`\n",
    "    - 三个Numpy数组: `indices`、`indptr`、`data`\n",
    "        - `indices`是每个块列索引的数组\n",
    "        - `data`是形状为(nnz, R, C)对应的非零值\n",
    "        - ...\n",
    "    - `_cs_matrix`的子类 (通用的CSR/CSC功能性)\n",
    "    - `_data_matrix`的子类 (带有`data`属性的稀疏矩阵类)\n",
    "- 快速矩阵向量相乘和其他的算术 (sparsetools)\n",
    "- 构建器接受:\n",
    "    - 密集矩阵 (数组)\n",
    "    - 稀疏矩阵\n",
    "    - 形状元组 (创建空的矩阵)\n",
    "    - `(data, ij)`元组\n",
    "    - `(data, indices, indptr)`元组 \n",
    "- 许多对于带有密集子矩阵的稀疏矩阵算术操作比CSR更高效很多\n",
    "- 用途:\n",
    "    - 类似CSR\n",
    "    - 有限元素向量值离散化\n",
    "##### 2.5.2.2.7.1 示例\n",
    "\n",
    "- 创建空的`(1, 1)`块大小的（类似CSR...）的BSR矩阵:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 54,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<3x4 sparse matrix of type '<class 'numpy.int8'>'\n",
       "\twith 0 stored elements (blocksize = 1x1) in Block Sparse Row format>"
      ]
     },
     "execution_count": 54,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mtx = sparse.bsr_matrix((3, 4), dtype=np.int8)\n",
    "mtx "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 55,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "matrix([[0, 0, 0, 0],\n",
       "        [0, 0, 0, 0],\n",
       "        [0, 0, 0, 0]], dtype=int8)"
      ]
     },
     "execution_count": 55,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mtx.todense()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- 创建块大小`(3, 2)`的空BSR矩阵:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 59,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<3x4 sparse matrix of type '<class 'numpy.int8'>'\n",
       "\twith 0 stored elements (blocksize = 3x2) in Block Sparse Row format>"
      ]
     },
     "execution_count": 59,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mtx = sparse.bsr_matrix((3, 4), blocksize=(3, 2), dtype=np.int8)\n",
    "mtx"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "    - 一个bug?\n",
    "- 用`(1, 1)`块大小 (类似 CSR...)`(data, ij)`的元组创建:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 60,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<3x3 sparse matrix of type '<class 'numpy.int64'>'\n",
       "\twith 6 stored elements (blocksize = 1x1) in Block Sparse Row format>"
      ]
     },
     "execution_count": 60,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "row = np.array([0, 0, 1, 2, 2, 2])\n",
    "col = np.array([0, 2, 2, 0, 1, 2])\n",
    "data = np.array([1, 2, 3, 4, 5, 6])\n",
    "mtx = sparse.bsr_matrix((data, (row, col)), shape=(3, 3))\n",
    "mtx "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 61,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "matrix([[1, 0, 2],\n",
       "        [0, 0, 3],\n",
       "        [4, 5, 6]], dtype=int64)"
      ]
     },
     "execution_count": 61,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mtx.todense()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 62,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([0, 2, 2, 0, 1, 2], dtype=int32)"
      ]
     },
     "execution_count": 62,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mtx.indices"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 63,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([0, 2, 3, 6], dtype=int32)"
      ]
     },
     "execution_count": 63,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mtx.indptr"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- 用`(2, 1)`块大小`(data, indices, indptr)`的元组创建:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 64,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "matrix([[1, 1, 0, 0, 2, 2],\n",
       "        [1, 1, 0, 0, 2, 2],\n",
       "        [0, 0, 0, 0, 3, 3],\n",
       "        [0, 0, 0, 0, 3, 3],\n",
       "        [4, 4, 5, 5, 6, 6],\n",
       "        [4, 4, 5, 5, 6, 6]])"
      ]
     },
     "execution_count": 64,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "indptr = np.array([0, 2, 3, 6])\n",
    "indices = np.array([0, 2, 2, 0, 1, 2])\n",
    "data = np.array([1, 2, 3, 4, 5, 6]).repeat(4).reshape(6, 2, 2)\n",
    "mtx = sparse.bsr_matrix((data, indices, indptr), shape=(6, 6))\n",
    "mtx.todense()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 65,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[[1, 1],\n",
       "        [1, 1]],\n",
       "\n",
       "       [[2, 2],\n",
       "        [2, 2]],\n",
       "\n",
       "       [[3, 3],\n",
       "        [3, 3]],\n",
       "\n",
       "       [[4, 4],\n",
       "        [4, 4]],\n",
       "\n",
       "       [[5, 5],\n",
       "        [5, 5]],\n",
       "\n",
       "       [[6, 6],\n",
       "        [6, 6]]])"
      ]
     },
     "execution_count": 65,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "data"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2.5.2.3 总结\n",
    "\n",
    "存储机制的总结\n",
    "\n",
    "\n",
    "|格式|矩阵 * 向量|提取项目|灵活提取|设置项目|灵活设置|求解器|备注|\n",
    "|------|---------------|--------|---------|--------|---------|-------|----|\n",
    "|DIA|sparsetools|.|.|.|.|迭代|有数据数组，专门化|\n",
    "|LIL|通过 CSR|是|是|是|是|迭代|通过CSR的算术, 增量构建|\n",
    "|DOK|python|是|只有一个轴|是|是|迭代|`O(1)`条目访问, 增量构建|\n",
    "|COO|sparsetools|.|.|.|.|迭代|有数据数组, 便利的快速转换|\n",
    "|CSR|sparsetools|是|是|慢|.|任何|有数据数组, 快速以行为主的操作|\n",
    "|CSC|sparsetools|是|是|慢|.|任何|有数据数组, 快速以列为主的操作|\n",
    "|BSR|sparsetools|.|.|.|.|专门化|有数据数组，专门化|"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
